package features.advance.leetcode.compete;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 *  1665. 完成所有任务的最少初始能量
 *
 *  难度：困难
 *
 * 给你一个任务数组 tasks ，其中 tasks[i] = [actuali, minimumi] ：
 *
 * actuali 是完成第 i 个任务 需要耗费 的实际能量。
 * minimumi 是开始第 i 个任务前需要达到的最低能量。
 * 比方说，如果任务为 [10, 12] 且你当前的能量为 11 ，那么你不能开始这个任务。如果你当前的能量为 13 ，你可以完成这个任务，且完成它后剩余能量为 3 。
 *
 * 你可以按照 任意顺序 完成任务。
 *
 * 请你返回完成所有任务的 最少 初始能量。
 *
 *
 *
 * 示例 1：
 *
 * 输入：tasks = [[1,2],[2,4],[4,8]]
 * 输出：8
 * 解释：
 * 一开始有 8 能量，我们按照如下顺序完成任务：
 *     - 完成第 3 个任务，剩余能量为 8 - 4 = 4 。
 *     - 完成第 2 个任务，剩余能量为 4 - 2 = 2 。
 *     - 完成第 1 个任务，剩余能量为 2 - 1 = 1 。
 * 注意到尽管我们有能量剩余，但是如果一开始只有 7 能量是不能完成所有任务的，因为我们无法开始第 3 个任务。
 * 示例 2：
 *
 * 输入：tasks = [[1,3],[2,4],[10,11],[10,12],[8,9]]
 * 输出：32
 * 解释：
 * 一开始有 32 能量，我们按照如下顺序完成任务：
 *     - 完成第 1 个任务，剩余能量为 32 - 1 = 31 。
 *     - 完成第 2 个任务，剩余能量为 31 - 2 = 29 。
 *     - 完成第 3 个任务，剩余能量为 29 - 10 = 19 。
 *     - 完成第 4 个任务，剩余能量为 19 - 10 = 9 。
 *     - 完成第 5 个任务，剩余能量为 9 - 8 = 1 。
 * 示例 3：
 *
 * 输入：tasks = [[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]]
 * 输出：27
 * 解释：
 * 一开始有 27 能量，我们按照如下顺序完成任务：
 *     - 完成第 5 个任务，剩余能量为 27 - 5 = 22 。
 *     - 完成第 2 个任务，剩余能量为 22 - 2 = 20 。
 *     - 完成第 3 个任务，剩余能量为 20 - 3 = 17 。
 *     - 完成第 1 个任务，剩余能量为 17 - 1 = 16 。
 *     - 完成第 4 个任务，剩余能量为 16 - 4 = 12 。
 *     - 完成第 6 个任务，剩余能量为 12 - 6 = 6 。
 *
 *
 * 提示：
 *
 * 1 <= tasks.length <= 105
 * 1 <= actuali <= minimumi <= 104
 *
 * @author LIN
 * @date 2021-05-21
 */
public class Compete1665 {

    public static void main(String[] args) {
        Solution solution = new Solution() {
                @Override
                public int minimumEffort(int[][] tasks) {
                    // 一个任务有：所需能量 和 最低能量
                    // 求：最小的起始能量
                    // 先完成 最低能量 和 所需能量 差值最大的。余下金额可能多的能量给下一个任务用
                    // 差值相同的，先完成 最低能量大的
                    int n = tasks.length;
                    PriorityQueue<Task> pq = new PriorityQueue<>(new Cmp());
                    for (int i = 0; i < n; i++) {
                        int actual = tasks[i][0];
                        int min = tasks[i][1];
                        pq.add(new Task(actual, min, min - actual));
                    }
                    int init = 0;
                    int left = 0;
                    while (!pq.isEmpty()) {
                        Task task = pq.poll();
                        int actual = task.actual;
                        int min = task.min;
                        if (left >= min) {
                            left -= actual;
                        } else {
                            init = init + (min - left);
                            left = min - actual;
                        }
                    }
                    return init;
                }

            class Cmp implements Comparator<Task> {
                @Override
                public int compare(Task t1, Task t2) {
                    if (t1.diff == t2.diff) return t2.min - t1.min;
                    return t2.diff - t1.diff;
                }
            }
            class Task {
                int actual;
                int min;
                int diff;

                public Task(int actual, int min, int diff) {
                    this.actual = actual;
                    this.min = min;
                    this.diff = diff;
                }
            }
        };
        int[][] tasks = {{1,2},{2,4},{4,8}};
        int minimumEffort = solution.minimumEffort(tasks);
        System.out.println(minimumEffort);
    }
    static class Solution {
        /**
         *  题解中大部分的篇幅为公式，请读者认真仔细阅读。
         *
         * 方法一：自定义排序
         * 思路与算法
         *
         * 设完成所有任务需要的能量为 p，这些任务依次为 (a0,m0), (a1, m1),..., (an-1, mn-1)，那么根据题目的要求，有：
         *
         * p >= m0
         * p - a0 >= m1
         * p - a1 - a0 >= m2
         * ...
         * p - an-2 - an-1 - ... -a2 - a1 >= mn-1
         *
         * 将与 p 无关的项都移至不等式的右侧，整理得：
         *
         * p>=m0
         * p>=a0+m1
         * p>=a1+a0+m2
         * ...
         * p>=an-2+an-1+...+a2+a1+mn-1
         *
         * 由于我们需要计算出最少的能量，因此我们的目标是上面 n 个不等式右侧的最大值最小，此时 p 就是这个最大值。
         *
         * 那么我们如何最小化这个最大值呢？首先可以尝试「局部最优解」，我们来看一看如果交换相邻两个任务的顺序，会发生什么。
         * 假设我们交换了任务 (ai, mi)以及 (ai+1,mi+1)
         * ，那么只有交换前：
         *
         *
         *
         * 以及交换后：
         *
         *
         * 的包含 m_im
         *   或者 m_{i+1}m
         *
         *   的这两个不等式产生了变化，其余不等式在交换前后均保持不变。因此，如果在交换后，
         *   不等式右侧（仅考虑这两个变化的不等式，而不是考虑所有的不等式）的最大值更小了，那么交换显然不会使得答案更差。
         *
         * 这是因为如果这两个变化的不等式右侧的最大值变小了，那么所有的 nn 个不等式右侧的最大值要么也变小，要么保持不变，因此交换不会使得答案更差。
         *
         * 交换前的最大值为 \max \big\{ P(i,0),P(i,1) \big\}max{P(i,0),P(i,1)}，交换后的最大值为 \max \big\{ P'(i,0),P'(i,1) \big\}max{P
         * ′
         *  (i,0),P
         * ′
         *  (i,1)}。由于 P(i,0) < P'(i,1)P(i,0)<P
         * ′
         *  (i,1) 以及 P'(i,0) < P(i,1)P
         * ′
         *  (i,0)<P(i,1) 恒成立，因此交换的条件：
         *
         * \max \big\{ P(i,0),P(i,1) \big\} > \max \big\{ P'(i,0),P'(i,1) \big\}
         * max{P(i,0),P(i,1)}>max{P
         * ′
         *  (i,0),P
         * ′
         *  (i,1)}
         *
         * 等价于：
         *
         * P(i,1) > P'(i,1)
         * P(i,1)>P
         * ′
         *  (i,1)
         *
         * 将不等式的右侧带入并消去相同项，就可以得到：
         *
         * a_i+m_{i+1} > a_{i+1}+m_i
         * a
         * i
         * ​
         *  +m
         * i+1
         * ​
         *  >a
         * i+1
         * ​
         *  +m
         * i
         * ​
         *
         *
         * 也就是：
         *
         * a_i - m_i > a_{i+1} - m_{i+1}
         * a
         * i
         * ​
         *  −m
         * i
         * ​
         *  >a
         * i+1
         * ​
         *  −m
         * i+1
         * ​
         *
         *
         * 因此，对于任意一种安排任务的方式，我们不断找出满足 a_i - m_i > a_{i+1} - m_{i+1}a
         * i
         * ​
         *  −m
         * i
         * ​
         *  >a
         * i+1
         * ​
         *  −m
         * i+1
         * ​
         *   的相邻的两个任务，并将它们进行交换，就可以使得答案不会更差。当我们无法找出满足 a_i - m_i > a_{i+1} - m_{i+1}a
         * i
         * ​
         *  −m
         * i
         * ​
         *  >a
         * i+1
         * ​
         *  −m
         * i+1
         * ​
         *   的相邻的两个任务时，就得到了一个「局部最优解」。
         *
         * 那么我们如何得到「全局最优解」（也就是答案）呢？实际上，「局部最优解」就是「全局最优解」，因为对于任意的两个任务索引 i,ji,j，a_i-m_ia
         * i
         * ​
         *  −m
         * i
         * ​
         *   和 a_j-m_ja
         * j
         * ​
         *  −m
         * j
         * ​
         *   的大小关系都是可比较的，因此对于所有的「局部最优解」，它们都是将这些任务按照ai-mi>ai+1-mi+1
         *   升序排序得到的结果，只是在有相同的ai-mi>ai+1-mi+1
         *   时，不同的「局部最优解」对它们的排列顺序不相同，但这并不会影响最终答案。
         *
         * 因此，任意的「局部最优解」都是「全局最优解」。当然我们也不必真的模拟「局部最优解」的求解过程，而是可以直接将所有的任务按照 ai-mi>ai+1-mi+1
         *
         *   升序排序，并计算出答案即可。
         *
         * 作者：zerotrac2
         * 链接：https://leetcode-cn.com/problems/minimum-initial-energy-to-finish-tasks/solution/wan-cheng-suo-you-ren-wu-de-zui-shao-chu-shi-neng-/
         * 来源：力扣（LeetCode）
         * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
         *
         * @param tasks
         * @return
         */
        public int minimumEffort(int[][] tasks) {
            /**
             * 先从mi-ai差值大的任务开始
             *
             */
            Arrays.sort(tasks, (o1, o2) -> {
                if(o1[1] - o1[0] == o2[1] - o2[0]){
                   if(o2[1] > o1[1]){
                       return 1;
                   }else if(o2[1] == o1[1]){
                       return 0;
                   }else {
                       return -1;
                   }
                }else if(o1[1] - o1[0] < o2[1] - o2[0]){
                    return 1;
                }else{
                    return -1;
                }
            });
            int n = tasks[0][1];
            int a = 0;
            for (int[] task : tasks) {
                if(n - a < task[1]){
                    n+=task[1] - n + a;
                }
                a+=task[0];
                System.out.println(Arrays.toString(task));
            }
            return n;
        }
    }
}
/**
 *           n
 * [10, 12] 12            10    2
 * [2, 4]   12+4-2=14     12    2
 * [1, 3]   14+3-2=15     13    2
 * [10, 11] 2+11-2+15=26  23    3
 * [8, 9]   26+9-3=32     31    1
 */